package NewCoder;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class BM27 {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(pRoot==null) return res;
        Deque<TreeNode> q=new LinkedList<>();
        q.add(pRoot);
        int flag=1;
        while(!q.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            int n=q.size();
            for(int i=0;i<n;i++){
                if(flag%2==0){
                    TreeNode p1=q.pollLast();
                    list.add(p1.val);
                    if(p1.right!=null) q.addFirst(p1.right);
                    if(p1.left!=null) q.addFirst(p1.left);
                }else {
                    TreeNode p2 = q.pollFirst();
                    list.add(p2.val);
                    if (p2.left != null) q.addLast(p2.left);
                    if (p2.right != null) q.addLast(p2.right);
                }
            }
            flag++;
            res.add(list);
        }
        return res;
    }
}
